Cellular automata are computational logic cells that form the building blocks for cellular computational networks (or cellular automatom). Such cellular networks are commonly used as the computational engines for implementing parallel processing operations.
A cellular network is an interconnection of identical logic cells, where a cell is a finite state machine. Each cell receives inputs from a finite set of neighbor cells, and possibly from an external source. All cells compute one output simultaneously each clock cycle, with each cell providing its output also to a set of neighbor cells, and possibly to an external receiver.
The specific problem to which the invention has application is the design of new cellular automata that can be assembled into cellular networks for parallel processing. These cellular automata should be useful in the design and assembly of complex cellular networks for such applications as signal processing and artificial intelligence.
A large body of problems in signal processing and artificial intelligence can only be solved computationally by exploiting significant amounts of parallelism. The computational approach to these problems typically involves performing such tasks as graph searching and spatial filtering which are particularly amenable to parallel processing.
For a number of these applications, cellular automata have been assembled into computer architectures for parallel processing. Recently, interest in computer architectures based on cellular automata has increased because of the significant potential for VLSI implementations.
However, initial attempts to use cellular automata assembled into linear systems for parallel processing have failed to meet expectations, and useful artificial intelligence problems remain for the most part computationally intractable. These systems have been found to be limited by their structures in the degree of parallelism they can practically achieve.
One common application far parallel processing systems is to solve artificial intelligence problems involving graph searching. Graph searching is required in a wide variety of artificial intelligence applications, including: Data base search, speech recognition (dynamic time warping), financial forecasting, operation management, trajectory planning, natural language interfaces, and learning systems.
Another typical application for parallel processing is two-dimensional spatial filtering such as for image recognition applications.
Accordingly, a need exists for new cellular automata that can be assembled into cellular computational networks, such as for implementing graph searching and spatial filtering in signal processing and artificial intelligence applications that use parallel processing.